#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 剑指 Offer 62. 圆圈中最后剩下的数字.py
@time: 2022/2/27 16:35
@desc: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
'''
class Solution(object):
    def lastRemaining(self, n, m):
        """
        :type n: int
        :type m: int
        :rtype: int
        """
        lis = list(range(n))
        # 记录当前位置
        i = 0
        while len(lis)>1:
            # 弹出位置, 注意到lis的长度时刻在变化
            i = (i+m-1)%len(lis)
            # 弹出
            lis.pop(i)
        return lis[0]

if __name__ == '__main__':
    res = Solution().lastRemaining(82002, 120659)
    print(res)